#ifndef RADIX_SORT
#define RADIX_SORT


// good
template<class Type>
int MaxDigits(Type array [] , int length){
	int d = 1 , i ;	Type max = 10;
	for( i = 0 ; i < length ; ++i){
		while(array[i] > max){
			max *= 10;		d++;	
		}
	}
   return d;	
}

//not very good
template<class Type>
int MaxDigits2(Type array [] , int length){
	int d = 1 , i ;	Type max = 10;
	while(true){
		for( i = 0 ; i < length ; ++i){
			if(array[i] > max){
				max *= 10;		d++;		break;
			}
		}
		if( i == length)return d;
	}
}

//http://baike.baidu.com/view/1170573.htm
template<class Type,int Length>
void RadixSort(Type (&array) [Length] ){
	const int digits = 10;
	int count [digits] = {0};
	Type * tempArray = new Type [Lenght];
	int maxDigits = MaxDigits(array,Length);

	int radix = 1;
	int digit;
	for(int i = 0 ; i < maxDigits ; ++i , radix *= 10){
		         // initialize to zeroes
		        for(int c = 0 ; c < digits ; ++c) 
			          count[c] = 0;

				//count the numbers of a given digit
				for(int n = 0 ; n < Length ; ++n){
					digit = (array[n]/radix) %10; //  (array[n] % (radix*10)) / radix; works as well , but not good enough
					count[digit]++;
				}

				// map digit count result to the position of tempArray
				for(int c = 1 ; c < digits ; ++c) 
			          count[c] += count[c - 1];

				// "sorting"
				for(int n = Length - 1 ; n >=0 ; -- n){ // start from the back of the array;
					digit = (array[n]/radix) % 10;
					tempArray [ count[digit] ]  = array[n];
					count[digit]--;                                 // "--" is the reason why goes from back
					// the "count" array is now storing  the new position 
				}


				// copy result
				for(int n = Length - 1 ; n >=0 ; -- n){
					array[ n ] = tempArray [n];
				}		
	}
	delete [] tempArray;

}
#endif